package com.gxc.array;

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值。
 * 要求时间复杂度0(N)，且要求不能用非基于比较的排序。
 *
 * 解法：
 * 1.暴力破解，先排序再计算邻近的差值。时间复杂度最小n*log(n)  --快排，归并，堆排。
 * 2.利用桶的思想
 * 数组有n个数，准备n+1的桶
 * 首先遍历数据，找到数组中的最大值和最小值，min,max
 * 把min放入第0个桶，max放入第n个桶
 * 遍历数据剩余的值，根据每个桶放  （max-min）/n  的数值规则放入桶内---第i个桶范围  min+（max-min）/n * i~min+（max-min）/n * (i+1)
 * 由于有n+1个桶，所以必定有桶是没有值，所以相邻的最大值必定不在桶内。（桶内的最大差值是 （max-min）/n）,
 * 只需关注两个桶的最大值和最小值
 * 建立三个数组，
 * havenum[] 桶内是否有值，
 * maxnum[] 桶的最大值
 * minnum[] 桶的最小值
 * 根据规则放入桶中，遍历左桶的最大值和右桶的最小值
 */
public class NearMax {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4 ,5 ,7, 8};
        System.out.println(maxGap(arr));
    }

    /**
     *
     * @return
     */
    public static int maxGap(int[] arr) {
        if (arr == null || arr.length == 0) return 0;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        //如果最大值和最小值相等
        if (max == min) return 0;

        int gap = 0;
        int n = arr.length;
        boolean[] havenum = new boolean[n+1];
        int[] maxnum = new int[n+1];
        int[] minnum = new int[n+1];

        //桶的坐标
        int loc = 0;
        for (int i = 0; i < arr.length; i++) {
            loc = location(arr[i], n, max, min);
            //判断原来是否有值
            maxnum[loc] = havenum[loc]?Math.max(maxnum[loc], arr[i]):arr[i];
            minnum[loc] = havenum[loc]?Math.min(minnum[loc], arr[i]):arr[i];
            havenum[loc] = true;
        }

        int preMax = maxnum[0];
        for (int i = 1; i < havenum.length; i++) {
            if (havenum[i]) {
                gap = Math.max(gap, minnum[i] - preMax);
                preMax = maxnum[i];
            }
        }

        return gap;
    }

    private static int location(int cur, int n, int max, int min) {
        return (cur-min) * n /(max-min);
    }


}
